package com.xhj.joffer.stack;

import java.util.*;
/** @author haijianxia pure_xhj@163.com @Date 2021-09-15 @Time 15:27 */
public class StackFindMin {
  public static void main(String[] args) {
    Stack stack = new Stack(3, 1, 5, 7, 3, 2);
    System.out.println(stack.toString());
    System.out.println("stack.findMin() = " + stack.findMin());

    stack.pop();
    stack.pop();
    stack.pop();
    System.out.println("after pop:");
    System.out.println(stack.toString());
    System.out.println("stack.findMin() = " + stack.findMin());

    stack.push(-1);
    stack.push(0);
    stack.push(1);
    System.out.println("after push:");
    System.out.println(stack.toString());
    System.out.println("stack.findMin() = " + stack.findMin());

    System.out.println("==========================stack3==========================");
    Stack3 stack3 = new Stack3(3, 1, 5, 7, 3, 2);
    System.out.println(stack3.toString());
    System.out.println("stack3.findMin() = " + stack3.findMin());

    stack3.pop();
    stack3.pop();
    stack3.pop();
    System.out.println("after pop:");
    System.out.println(stack3.toString());
    System.out.println("stack3.findMin() = " + stack3.findMin());

    stack3.push(-1);
    stack3.push(0);
    stack3.push(1);
    System.out.println("after push:");
    System.out.println(stack3.toString());
    System.out.println("stack3.findMin() = " + stack3.findMin());

    stack3.popAll();
    System.out.println("after pop all: ");
    System.out.println(stack3.toString());
    System.out.println("stack3.findMin() = " + stack3.findMin());
  }

  private static class Stack {
    public Stack() {}
    public Stack(ArrayList<Integer> list) {
      for (int i = 0; i < list.size(); i++) {
        this.push(list.get(i));
      }
    }
    public Stack(int... i) {
      for (int i1 = 0; i1 < i.length; i1++) {
        this.push(i[i1]);
      }
    }

    private ArrayList<Integer> list = new ArrayList();
    private ArrayList<Integer> listSorted = new ArrayList();
    // 维系一个有序数组
    // push时, 更新有序数组
    // 弹出时, 更新有序数组

    private void push(int value) {
      list.add(value);
      ArrayList<Integer> listTemp = new ArrayList();
      if (listSorted.size()==0){
        listTemp.add(value);
      }else {
        int times=1;
        for (int i = 0; i < listSorted.size(); i++) {
          if (times==1 && value<listSorted.get(i)) {
            listTemp.add(value);times=0;
          }
          listTemp.add(listSorted.get(i));
        }
        if (times==1){
          listTemp.add(value);
        }
      }
      listSorted=listTemp;
    }

    private int pop() {
      int value = list.get(list.size() - 1);
      list.remove(list.size() - 1);
      ArrayList<Integer> listTemp = new ArrayList();
      int times=1;
      for (int i = 0; i < listSorted.size(); i++) {
        if (listSorted.get(i) == value && times==1) {
          times=0; continue;
        }
        listTemp.add(listSorted.get(i));
      }

      listSorted=listTemp;
      return value;
    }

    private int findMin() {
      return listSorted.get(0);
    }
    @Override
    public String toString() {
      return "origin: "+list.toString()+"\nsorted: "+listSorted.toString();
    }
  }
  /**
   * 思路三: 使用数组
   */
  private static class Stack3{
    int[] stack;
    int[] stackSort;

    public Stack3() {
    }
    public Stack3(ArrayList<Integer> list) {
      stack=new int[list.size()];
      for (int i = 0; i < list.size(); i++) {
        push(list.get(i));
      }
    }
    public Stack3(int... array) {
      for (int i = 0; i < array.length; i++) {
        push(array[i]);
      }
    }

    public void push(int value){
      if (stack == null) {
        stack= new int[]{value};
        stackSort= new int[]{value};
        return;
      }
      int lengthTemp = stack.length + 1;
      int[] stackTemp=new int[lengthTemp];
      for (int i = 0; i < stack.length; i++) {
        stackTemp[i]=stack[i];
      }
      stackTemp[lengthTemp-1]=value;

      // 小则插入
      int[] stackSortTemp=new int[lengthTemp];
      int indexTemp=0, times=1;
      for (int i = 0; i < lengthTemp-1; i++) {
        if (times==1 && value<stackSort[i]){
          stackSortTemp[indexTemp++]=value;times=0;
        }
        stackSortTemp[indexTemp++]=stackSort[i];
      }
      if (times == 1) {
        stackSortTemp[indexTemp++]=value;
      }

      // 更新
      stack=stackTemp;
      stackSort=stackSortTemp;
    }

    public int pop(){
      int value=0;
      if (stack==null && stack.length==0){
        throw new NullPointerException("当前栈为空");
      }

      int lengthTemp = stack.length - 1;

      // stack 弹出末尾元素
      int[] stackTemp=new int[lengthTemp];
      for (int i = 0; i < lengthTemp; i++) {
        stackTemp[i]=stack[i];
      }

      value=stack[stack.length -1];

      // 等则删除
      int[] stackSortTemp=new int[lengthTemp];
      int indexTemp=0, times=1;
      for (int i = 0; i < stack.length; i++) {
        if (times==1 && value==stackSort[i]){
          times=0;continue;
        }
        stackSortTemp[indexTemp++]=stackSort[i];
      }

      // 更新
      stack=stackTemp;
      stackSort=stackSortTemp;

      return value;
    }

    public void popAll() {
      int times=stack.length;
      for (int i = 0; i < times; i++) {
        pop();
      }
    }

    public int findMin(){
      if (stack.length==0){
        throw new NullPointerException("当前栈为空");
      }
      return stackSort[0];
    }

    @Override
    public String toString(){
      return "stack: "+Arrays.toString(stack)+"\nstackSort: "+Arrays.toString(stackSort);
    }
  }

}
